1. Field of the Invention
The present invention relates to network protocols and network intermediate devices executing such protocols; and more particularly to algorithms for managing a tree of network devices for a data network according to a spanning tree protocol.
2. Description of Related Art
Local area networks LANs specified according to IEEE Standards for Local and Metropolitan Area Networks under section 802.x of all types may be connected together with media access control MAC bridges. Bridges interconnect LAN segments so that stations connected to the LANs operate as if they were attached to a single LAN for many purposes. Thus a bridged local area network provides for interconnection of stations attached to LAN segments of different MAC types, for an increase in the physical extent, the number of permissible attachments and the total performance of a LAN, and for the partitioning of physical LAN support for administrative or maintenance reasons. The MAC bridge is specified according to the IEEE standard 802.1D (IEEE Std 802.1D-1990, IEEE Standards for Local and Metropolitan Area Networks: Media Access Control (MAC) Bridges.)
When a bridged network is established, it is possible to create loops in the network by providing more than one path through bridges and LAN segments between two points. Thus, according to the 802.1D standard, an active topology for the bridged network is maintained according to the spanning tree protocol which is described in the standard. The spanning tree protocol automatically establishes a fully connected (spanning) and loop-free (tree) bridged network topology. It uses a distributed algorithm that selects a root bridge and the shortest path to that root from each LAN. Tie breakers are used to ensure that there is a unique shortest path to the root, while uniqueness of the root is guaranteed by using one of its MAC addresses as part of a priority identifier.
Every LAN in the network has one and only one "designated port" providing that LANs shortest path to the root, through the bridge of which the designated port is a part. The bridge is known as the designated bridge for that LAN.
Thus, bridges other than the root bridge at the root of the network can be termed a branch bridge. Every branch bridge has a "root port" which is the port providing that bridge's shortest path to the root. Ports other than the root port are designated ports, or alternate ports according to the standard. An alternate port is connected to a LAN that for which another bridge is the designated bridge, and is placed in a blocking state so that frames are not forwarded through that port.
The frame forwarding path through any bridge is thus between its root port and designated ports. When spanning tree information has been completely distributed and is stable, this connectivity will connect all of the LANs in a loop free tree.
When a bridge first receives spanning tree information that dictates new connectivity through that bridge, it does not establish the new connectivity immediately. Ports that were connected previously as either the root port or a designated port, but are no longer to be connected, are immediately made blocking. However the transition to a forwarding state of ports that were previously not connected in a forwarding role is delayed. The delay serves two purposes:
(a) Frames forwarded on the previous topology may still be buffered by bridges in the network. Thus an instantaneous bridge to the new topology can cause these to be forwarded back to their LAN of origin, causing duplication of the frame once. PA1 (b) New spanning tree information in the network may not have been filly distributed yet. Thus an immediate change to a new topology may cause temporary loops. These loops could generate high traffic volumes, disrupting end stations, causing frame loss in bridges, and possibly delaying the propagation of spanning tree information further. PA1 message age time&lt;T&lt;message age time+2*forward delay time
The first of these two reasons (a), is far less important than it once was, since the protocols prevalent on LANs today deal with immediately duplicated frames. Some old implementations of LLC type 2 will reset connection under these circumstances, but they are no longer in wide spread deployment. Thus the issue presented by reason (a) is less important.
Reason (b) continues to be a fundamental to the spanning tree configuration.
According to the spanning tree protocol of the standard, each port on a bridge can assume a blocking state in which frames are not forwarded through the port, a forwarding state in which frames are forwarded through the port. For a transition from the blocking state to the forwarding state, the protocol requires the port to proceed through transitional states referred to as the listening state and the learning state. In the listening state, the port is preparing to participate in frame relay, however frame relay is temporarily disabled to prevent temporary loops. In the listening state, the port monitors bridge protocol data unit (BPDU) frames or other information related to the topology in the network for an interval referred to as the forward delay timer. If no information is received which causes a change in state of the port before expire of the forward delay timer, then the port transitions to the learning state.
In the learning state, the port continues to prepare for participation in frame relay. The relay is temporarily disabled to prevent loops. In this state, in addition to monitoring BPDU frames and other information related to operation of the spanning tree algorithm, the port learns information about end stations that are accessible through the port for use in the forwarding of frames once the frame enters the forwarding state. Upon expiration of the forward delay timer in the learning state, if no better information about the protocol is received, then the port assumes the forwarding state. Thus, the transition from a blocking state to the forwarding state takes two times the forward delay timer interval. From the time of detection of a change in topology causing a transition from the blocking to the forwarding state, until the time in which the forwarding state is assumed can be a significant amount of time, as much as 20 to 50 seconds in some cases.
For background information consider bridge initialization, the addition of a link, and link failure situations according to the spanning tree protocol.
On bridge initialization, the bridge becomes the Root (with root path cost of zero). The root port identity stored by the bridge is reserved (value 0). All the ports on the bridge become designated ports for the respective segments and go through the transition (blocking.fwdarw.listening.fwdarw.learning) before they start forwarding data packets. A BPDU is generated on all the connected ports with the advertising bridge as the root as well as designated bridge and with the transmitting port as the designated port for the segment.
On each segment, if the advertising bridge is the highest priority (higher priority than that recorded as the designated root by the receiving port), the receiving port updates the root and designated bridge information (the root bridge, root path cost, designated bridge, and designated port) and starts the message age timer. The root information (the root bridge and root path cost) is updated on the receiving bridge. The designated ports are selected next relative to the new root information. The designated ports should remain designated and update their root and designated bridge information while some blocked ports might become designated now as a result of receiving information from a higher priority bridge. The blocked ports go through the transition (blocked.fwdarw.listening.fwdarw.learning) before they start forwarding data packets. If this new information is heard on the root port by a receiving bridge, it generates a configuration BPDU to be sent out on all the designated ports with the new root information. This way new root information is propagated along all branches of spanning tree and after a while all the bridges have a consistent view of the Root and corresponding root path costs.
If the advertising bridge has lower priority than the designated root recorded on the segment, only the designated bridge/port responds with the correct (superior) information. Once the correct (better) information is heard back by the advertising bridge, it updates the root and designated bridge information on all the ports as described in the above paragraph. If the spanning tree topology was stable before the advertising bridge came on line, only one response from one of the neighbors (designated bridge) should bring the advertising bridge in sync with other bridges regarding the Root identity. The first receiving port becomes the new root port and all other ports as the designated ports. Then the advertising bridge transmits a configuration BPDU on all the (now) designated ports advertising the newly learned root and root path cost. If the new information is better than that recorded previously on a segment, it replaces the old information and propagated further. Otherwise, the designated bridge responds and eventually all the ports move to the right status (alternate/designated/root).
As can be seen, good information is propagated quickly throughout the spanning tree. But, no forwarding takes place before ports go into forwarding state (blocking.fwdarw.listening.fwdarw.learning.fwdarw.forwarding).
On addition of a link, (or on port enablement) the port to which the link is added becomes the designated port for the connected segment and goes through the transition (blocking.fwdarw.listening.fwdarw.learning) before it starts forwarding data packets. The port takes the designated root and root path cost information from the bridge. Next time around when the bridge receives a hello packet on the root port, a hello packet is also generated for this new designated port. If there is another bridge on the connected segment providing better root path information, it responds and the usual designated bridge/port selection process takes place. If the received information is better than the current root information, root port and designated ports selection takes place. This process continues downstream until all the bridges have learned about the better root information. However, no forwarding takes place before the port goes into forwarding state (blocking.fwdarw.listening.fwdarw.learning). So, essentially the connectivity is established after 2*forward delay time (.about.30 seconds).
If a link failure occurs on the root port, the bridge reconfigures itself. Otherwise, the link failure (designated/blocked port) is ignored. Failure of a blocked port doesn't do any harm, but a designated port failure on a bridge indirectly affects its neighbors. Those neighbors who reach the root through the failed designated port, i.e., whose root port is on the same segment, eventually time out the information learned on the root port (through the message age timer expire). Once the message age timer expires, the bridge reconfigures itself. Reconfiguration can happen immediately following the root port failure (loss of linkbeat) or after the message age timer on the root port expires.
Reconfiguration of a bridge involves selecting the root port and designated ports. The root port is chosen from among the blocked ports providing the best root information. The bridge root information (designated root and root path cost) is updated with the information learned on this new root port. The designated ports are selected next relative to this new root port. In a stable topology, all the existing designated ports remain designated although their root information is updated with the now inferior information. As long as the Root Bridge doesn't fail, all the remaining blocked ports remain blocked since their connected segments already have better paths to the root. The blocked port that was upgraded to root port status goes through the transition (blocking.fwdarw.listening.fwdarw.learning.fwdarw.forwarding) before it actually starts forwarding data packets. A forward delay timer is started on this port. If this bridge is not the Root Bridge, it will receive the hello packet from the Root periodically and will transmit that on all the designated ports. Any neighbor whose root port lies on the connected segment ignores this inferior root information. Since the root information is not updated on the root port of the neighboring bridges, the message age timer eventually expires. When the timer expires, the corresponding root port becomes the designated port and the neighboring bridge reconfigures itself.
Since the message age timer is synchronized in the spanning tree, it should expire at around the same time in all the downstream bridges. These bridges make the corresponding root ports designated and select a new root port (from among the blocked ports) and start advertising the root information. On a segment, the bridge with the best root information wins (becomes the designated bridge), other ports on this segment either become root ports or are blocked.
If the root port fails on a bridge, the bridge can immediately select a new root port, which then goes through the transition. If the topology is such that this new root port remains a root port, this port can go into forwarding after 2*forward delay timer (assuming no propagation and processing delays). In case one of the designated ports becomes the root port (after neighbors speak up), partial connectivity will be restored after message age time. If any of the blocked ports becomes designated then connectivity through that port will be restored after 2*forward delay time. Other bridges in the network can take anywhere from message age time (if the root port remains the same or one of the designated ports becomes the root port) to message age time+2*forward delay timer time (if one of the blocked ports becomes designated) to converge.
To summarize, convergence time will be
Keeping the current defaults, this translates to 20-50 seconds (assuming no propagation and processing delays).
The above relationship is true even when a designated port fails on a bridge and there is at least one neighbor on the connected segment with the root port. Failure of a blocked port doesn't affect the spanning tree.
Convergence of a bridged network in situations involving changing of spanning tree topology can therefore cause significant loss of service situations, particularly in networks that carry real time data. For example, the use of data networks and the Internet for audio and video transmissions of real time signals is increasing. Twenty to fifty second convergence times for these uses of the data network can cause unacceptable glitches. Accordingly, it is desirable to provide a technique to improve the availability of a bridged network in the face of changes in topology.